import java.util.*;

//Definition for singly-linked list.

public class Solution {
    public static void main(String[] args) {
        ListNode list1 = new ListNode(1);
        ListNode list2 = new ListNode(2);
        ListNode list3 = new ListNode(3);
        ListNode list4 = new ListNode(5);
        ListNode list5 = new ListNode(4);
        ListNode list6 = new ListNode(6);
        ListNode list7 = new ListNode(7);
        list1.next = list2;
        list2.next = list3;
        list3.next = null;
        list4.next = list5;
        list5.next = null;
        list6.next = list7;
        ArrayList<ListNode> lists = new ArrayList<>();
        lists.add(list1);
        lists.add(list4);
        lists.add(list6);
        ListNode listNode = mergeKLists(lists);
        while (listNode!=null){
            System.out.println("listNode.val = " + listNode.val);
            listNode = listNode.next;
        }
    }
    public static ListNode mergeKLists(ArrayList<ListNode> lists) {
        // 方法一
        // 全部加入到数组中，排序，然后存值返回首地址
        ArrayList<Integer> value = new ArrayList<>();
        // 存入数组
        for (int i = 0; i < lists.size(); i++) {
            ListNode listNode = lists.get(i);
            while (listNode!=null){
                value.add(listNode.val);
                listNode = listNode.next;
            }
        }
        // 排序
        Collections.sort(value);
        // 存值
        ListNode result = new ListNode(value.get(0));
        ListNode move = result;
        for (int i = 1; i < value.size(); i++) {
            move.next = new ListNode(value.get(i));
            move = move.next;
        }
        return result;
    }
}